
\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}

\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
%\usepackage[margin=3cm]{geometry}

%\renewcommand{\headheight}{16pt}

%\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 7}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
        \rule{\linewidth}{0.1mm}\\
 	%\HRule\\
%	\HRule\\[2cm]
	
\end{center}
\section{Exercise 7.1: Three-Phase Commit Protocol}
\subsection{3PC description}
\begin{itemize}
\item Phase 1
  \begin{itemize}
  \item[Coordinator]
    Sends 'can commit?' question to all participants. Waits for 'yes' from all participant. If doesn't get all, transaction is aborted.
  \item[Participant]
    Gets 'can commit?' from coordinator, replies with 'yes' message. If doesn't get any other messages, aborts the transaction.
  \end{itemize}
\item Phase 2
  \begin{itemize}
    \item[Coordinator]
      Sends to all participant global outcome of the transaction. Expects 'ACK' message from all. If doesn't get them, sends abort to all participants(transaction is aborted).
    \item[Participant]
      Gets transaction data, replies with 'ACK' message. If doesn't get anything, aborts the transaction. If time outs after sending 'ACK', commits the transaction.
  \end{itemize}
\item Phase 3
   \begin{itemize}
     \item[Coordinator]
       Sends 'commit' message to all participants.
     \item[Participant]
       Commits the transaction.
   \end{itemize}
\end{itemize}
\subsection{Independent recovery}
After recovery the coordinator after getting all 'ack' messages in 2. phase, commits the transaction. In all other states it aborts the transaction.
Participant commits the transaction after recovery if it failed after sending 'ACK' message in phase 2. In other states it aborts the transaction after recovery. This guarantees consistent state of data, because transaction is commited only if all participants send 'ACK' message in phase 2(we assume that at most one site can fail).
\section{Exercise 7.2: Global Deadlock Detection}
  This algorithm is like testing all the possible paths through the blocked transactions and finding if there's one that cause a cycle in a distributed graph structure. So it can report the deadlocks.\\\\
  However, for some cases when the degree of data contention is high, some deadlocks may not be detected.\\\\
  It won't report false deadlocks.\\\\
  Since Path pushing sends messages between nodes while edge chasing does between transactions. It depends on the number of nodes and transactions. Normally the edge chasing is faster, but when transactions are more than nodes, path pushing can be faster. Edge chasing is more flexible because path pushing has to form the whole WFG anyway. Also the messages sending in edge chasing are shorter than in path pushing.



\section{Exercise 7.3: Discussion}
1. The difference between materialized and virtual integration is data management. Materialized integration systems have a centralized database, while virtual integration ones have a decentralized database.\\\\
2. When local schema and component schema are the same, it means all the local schemas are the same.\\
When component schema and export schema are the same, it means the federated schema is the union of all the component schemas and no read or write access control to the component databases.\\
When all the three schemas are the same, it is like the 3-level architecture.\\
\section{Exercise 7.4: Mappings}
\begin{enumerate}[  a)]
 \item (Schema 1) --- (Schema 2)\\

    \begin{itemize}
     \item DB\_Course.Title == Courses.Title
     \item DB\_Course.Professor == Teaches.Professor
     \item DB\_Course.University == Courses.University
     \item DB\_Course.C ID ; Teaches.CourseID ; Courses.CourseID (same roles - primary or foreign key. but possible different values between schemas)
    \end{itemize}

 \item
\begin{verbatim}
CREATE VIEW DB_Course as
SELECT C.Title , T.Professor, C.CourseID AS C_ID, C.University
FROM Courses C, Teaches T
WHERE C.CourseID == T.CourseID
\end{verbatim}
---
\begin{verbatim}
CREATE VIEW Courses as
SELECT C_ID, Title, University
FROM DB_Course

CREATE VIEW Teaches as
SELECT C_ID, Professor, NULL, NULL, University
FROM DB_Course
\end{verbatim}



\end{enumerate}

\section{Exercise 7.5: LaV vs. GaV}
\begin{enumerate}[  a)]
 \item

\begin{itemize}
 \item Build buckets\\
\small
$\begin{array}{|l|}
\hline
Teaches(prof, course\_id, sem);\ sem >= WS08;\ course\_id > 300 \\
\hline
Enrolled(stud, course\_id, sem);\ sem >= WS08;\ course\_id > 300 \\
\hline
Courses(course\_id, title);\ course\_id > 300 \\
\hline
\end{array}$
\normalsize
 \item Sort views into matching buckets\\
\scriptsize
$\begin{array}{|l|}
\hline
Teaches(prof, course\_id, sem);\ sem >= WS08;\ course\_id > 300\\ \\
V1(s\_,prof,sem,course\_id),\ V3(prof, course\_id, t\_, sem),\ sem >= WS08,\ course\_id > 300 
 \\
\hline
Enrolled(stud, course\_id, sem);\ sem >= WS08;\ course\_id > 300 \\ \\
V1(stud,p\_,sem,course\_id),\ V3(p\_, course\_id, t_, sem),\ sem >= WS08,\ course\_id > 300 
\\
\hline
Courses(course\_id, title);\ course\_id > 300 \\ \\
V3(p\_, course\_id, title, s\_),\ course\_id > 300 \\
\hline
\end{array}$
\normalsize
\item Building combinations\\
$q_1(stud, course\_id, prof) :- V1(s\_,prof,sem,course\_id),\\ V1(stud,p\_,sem,course\_id),\\ V3(p\_, course\_id, title, s\_),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_2(stud, course\_id, prof) :- V1(s\_,prof,sem,course\_id),\\ V3(p\_, course\_id, t_, sem),\\ V3(p\_, course\_id, title, s\_),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_3(stud, course\_id, prof) :- V3(prof, course\_id, t\_, sem),\\ V1(stud,p\_,sem,course\_id),\\ V3(p\_, course\_id, title, s\_),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_4(stud, course\_id, prof) :- V3(prof, course\_id, t\_, sem),\\ V3(p\_, course\_id, t_, sem),\\ V3(p\_, course\_id, title, s\_),\\\ sem >= WS08,\ course\_id > 300$
\\
\item
$q_1(stud, course\_id, prof) :- V1(stud,prof,sem,course\_id),\\ V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_2(stud, course\_id, prof) :- V1(stud,prof,sem,course\_id),\\ V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_3(stud, course\_id, prof) :- V1(stud,prof,sem,course\_id),\\ V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$
\\\\
$q_4(stud, course\_id, prof) :- V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$
\\
\item Result:\\
$q_1(stud, course\_id, prof) :- V1(stud,prof,sem,course\_id),\\ V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$
\\
$UNION$
\\
$q_4(stud, course\_id, prof) :- V3(prof, course\_id, t\_, sem),\\\ sem >= WS08,\ course\_id > 300$

\end{itemize}



 \item
\begin{verbatim}
CREATE VIEW Teaches as
(SELECT professor as prof, c_id as course_id, semester as sem
FROM StudentsAndCourses1)
    UNION
(SELECT profNAme as prof, crs_id as course_id, semesterCode as sem
FROM ProfsAndCourses);


CREATE VIEW Enrolled as
SELECT sName as stud, course_id, semester
FROM StudentsAndCourses2 s2 LEFT OUTER JOIN
    (
        (SELECT c_id as course_id, semester FROM StudentsAndCourses1)
        UNION
        (SELECT crs_id as course_id, semesterCode FROM ProfsAndCourses)
    ) tmp1
WHERE s2.course_id == tmp1.course_id;


CREATE VIEW Courses as
SELECT crs_id as course_id, courseTitle as title
FROM ProfsAndCourses;
\end{verbatim}
\end{enumerate}


\end{document}
